#ifndef MGGS_GRAPH
#define MGGS_GRAPH


#include <iostream>
#include <cstdlib>
#include <climits>
#include "LinkedList.h"
#define inf INT_MAX

template<typename T>
class Graph
{
private:
    int V;
    class Side
    {
    public:
      int start;
      int end;
      T weight;
      Side* next;
      Side(int _start, int _end, T _weight);
    };
    Side* S;
public:
    Graph() {V = 0; S = NULL;};
    int get_point();
    void append_point();
    void set_point(int _V);
    void append_side(int _start, int _end, T _weight);
    void test_printout();
    T** adj_matrix();
    void test_adjm_printout();
    LinkedList<T>* adj_list();
    void test_adjl_printout();
};


template<typename T>
Graph<T>::Side::Side(int _start, int _end, T _weight){
  start = _start;
  end = _end;
  weight = _weight;
  next = NULL;
}

template<typename T>
int Graph<T>::get_point(){
  return V;
}

template<typename T>
void Graph<T>::append_point(){
  V++;
}

template<typename T>
void Graph<T>::set_point(int _V){
  V = _V;
}

template<typename T>
void Graph<T>::append_side(int _start, int _end, T _weight){
  if (_start <= V && _end <= V){
    Side* x = new Side(_start,_end,_weight);
    if (S == NULL)
      S = x;
    else{
      Side* p = S;
      while (p ->next != NULL)
	p = p->next;
      p->next = x;
    }
  }
}

template<typename T>
void Graph<T>::test_printout(){
  std::cout<< "number of vertex: " << V << std::endl;
  std::cout<< "side:" << std::endl;
  Side* p = S;
  while(p != NULL){
    std::cout << "("<< p->start << "," << p->end << "): " << p->weight << std::endl;
    p = p->next;
  }
}

template<typename T>
T** Graph<T>::adj_matrix(){
  T **M = new T* [V+1];
  for (int i=0; i<=V ; i++)
    M[i] = new T[V+1];
  for (int i=1; i<=V ; i++)
    for (int j=1; j<=V ; j++){
      if (i == j)
	M[i][j] = 0;
      else
	M[i][j] = inf;
    }
  Side* p = S;
  if (p != NULL){
    while (p->next != NULL){
      M[p->start][p->end] = p->weight;
      p = p->next;
    }
    M[p->start][p->end] = p->weight;
  }
  return M;  
}

template<typename T>
void Graph<T>::test_adjm_printout(){
  T** p = this->adj_matrix();
  for (int i=1; i<=V ; i++){
    for (int j=1; j<=V ; j++){
      if (*(*(p+i)+j) < inf)
	std::cout << *(*(p+i)+j) << "  ";
      else
	std::cout << "inf ";
    }
    std::cout <<"\b\b" << std::endl;
  }
}

template<typename T>
LinkedList<T>* Graph<T>::adj_list(){
  LinkedList<T>* L = new LinkedList<T>[V+1];
  Side* p = S;
  if (p != NULL){
    while (p->next != NULL){
      if (p->weight < inf)
	L[p->start].append(p->end,p->weight);
      p = p->next;
    }
    L[p->start].append(p->end,p->weight);
  }
  return L;
}

template<typename T>
void Graph<T>::test_adjl_printout(){
  LinkedList<T>* p = this->adj_list();
  if (V >= 1){
    for (int i=1; i<=V ; i++){
      std::cout << "vertex " << i << ":" << std::endl;
      p[i].list();
    }
  }
}

#else
// DO NOTHING.
#endif
